Description

给定一个 $n\times m$ 的网格，计算三个点都在格点上的三角形共有多少个。三角形的三点不能共线。
$n,m\leq 10^3$

Solution

Description

给定一棵有 $n$ 个节点的树。求对于每个 $k\in[0,n-1]$，有多少棵由这 $n$ 个点之间的边构造成的树，与给定的树恰好有 $k$ 条边重复。答案对 $10^9+7$ 取模。
$n\leq 100$

Solution

Description

给定 $n$ 个数 $a_1,\cdots, a_n$ ，求两两 $\text{lcm}$ 的最大值。
$1\leq n,a_i\leq 10^5$

Solution

Description

题面挺长的所以挂个链接

Solution

首先观察一下题面：它的值域不大。

Description

题面挺长挂个链接

Solution

「所有的鸽子都饱了」本质就是求每个鸽子第一次饱的时刻的最大值嘛，由于第一次本应是「最小」的含义，所以最值反演一手。

Description

给定 $n$ ，求下式的值

$\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{\text{lcm}(i,j)}{\text{gcd}(i,j)}$

Description

题面挺长的所以挂链接

Solution

听说这是两个经典 trick 的结合，mark 一下。

Description

给一个数列，每次随机从 $[1,m]$ 中选择一个数添加到数列末尾，直至数列的 $\gcd =1$ 时停止。求期望长度。
$1\leq m\leq 10^5$

Solution

T1 COCI2019 Quiz

Description

题面不长但是放个链接算惹

Solution

Description

给定一棵大小为 $n$ 的树，你需要给树上的点两两配对，对于一组对子 $(u,v)$ ，在树上将 $u\rightarrow v$ 的路径染色。定义一个配对方案合法当且仅当所有边都有颜色。
求方案数对 $10^9 + 7$ 取模。
$n\leq 5\times 10^3,2|n$